package hwOne3;

import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.StdOut;

import java.util.Scanner;

// 作业 1.3.9
public class CompleteExpression {
    public static void main(String[] args) {
        // 从标准输入读取表达式
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入缺少左括号的表达式：");
        String input = scanner.nextLine();
        scanner.close();

//        String input = "1 + 2 ) * 3 - 4 ) * 5 - 6 ) )";
        Stack<String> values = new Stack<>();
        Stack<String> operators = new Stack<>();

        // 遍历输入字符串的每个字符
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);

            // 忽略空格
            if (c == ' ') continue;

            // 如果是数字，直接压入操作数栈
            if (Character.isDigit(c)) {
                values.push(String.valueOf(c));
            }
            // 如果是运算符，压入运算符栈
            else if (c == '+' || c == '-' || c == '*' || c == '/') {
                operators.push(String.valueOf(c));
            }
            // 如果是右括号，弹出操作数和运算符，组成子表达式并压回操作数栈
            else if (c == ')') {
                // 弹出两个操作数和一个运算符
                String right = values.pop();
                String left = values.pop();
                String operator = operators.pop();
                StdOut.println("all operator:" + operator);
                // 构造新的子表达式
                String subExpression = "( " + left + " " + operator + " " + right + " )";

                // 将子表达式压入操作数栈
                values.push(subExpression);
            }
        }

        // 最终操作数栈中应该只剩下一个完整的表达式
        System.out.println("补全括号后的中序表达式：");
        System.out.println(values.pop());
    }
}
